1. Technical Field
The present invention relates to the field of firewalls implemented on networked computers, and more particularly, to reordering the rule-base within such firewalls for reducing central processing unit (CPU) usage of said firewalls.
2. Discussion of the Related Art
Firewalls are integrated collection of security measures designed to prevent unauthorized electronic access to a networked computer system. It may also assume the form of a device or set of devices configured to permit, deny, encrypt, decrypt, or proxy all computer traffic between different security domains based upon a set of rules and other criteria. Organizations that use internet protocol (IP) based communication networks have firewalls to control the traffic that crosses into and out of their networks, or between different network segments. Each firewall is basically a special-purpose computer that is enforcing the organization's traffic filtering policy. The filtering policy is implemented in a rule-base, which is an ordered list of rules. Each rule consists of a set of field value-ranges, and an associated action—which is typically either “PASS” or “DROP”.
Most firewalls enforce the policy according to “first-match” semantics: for each new IP connection, the firewall checks the rules one by one, according to their order in the rule-base, until it finds a rule that matches the new connection. The first rule that matches the connection determines the firewall's action: if the first matching rule has an action of “PASS” then the firewall will allow the connection to continue, and if the rule's action is “DROP” then the firewall will discard all the packets belonging to the connection. If no rule matches the connection then the firewall uses a default action, which is usually DROP.
Most firewalls implement the first-match semantics algorithm in software or firmware, using standard list or array data structures to maintain the rule-base. In such an implementation, the computational effort to match a connection to the rule-base is proportional (linearly) to the number rules the firewall needs to try in sequence until it reaches the first matching rule. If checking a match against one rule typically requires M computer instructions, then checking K rules in sequence requires K*M instructions. If the first-matching rule happens to be one of the first in the rule-base then the firewall will reach its action quickly and with a low computational effort. Conversely, if the first-matching rule is near the end of the rule-base, the firewall will work harder to reach an action.
The firewall's CPU utilization is the fraction of time that the firewall's CPU is actively executing commands that are part of its filtering activity (rather than waiting in an idle state). If the average utilization is high then the firewall may be unable to process all the connections attempting to go through it fast enough. If this occurs the firewall either drops connections indiscriminately, including connections that should be allowed according to the policy (this is a “fail-closed” strategy), or permits connections that should not be allowed (this is a “fail-open” strategy). Both failure types are undesirable, and it is one of the tasks of firewall administrators to ensure that neither failure occurs. Therefore, firewall administrators strive to keep the average firewall CPU utilization low, for example at 30% utilization or lower.
Clearly, the CPU utilization of a firewall depends on the speed of the CPU, on the general traffic load, and on the number of rules in the rule-base, but most crucially it depends on whether the order of the rules in the rule-base is tuned in the best possible way to the distribution of connections that the firewall is filtering. Specifically, if we wish to reduce the CPU utilization of the firewall, intuitively we would want to place the most popular rules (those that match large portions of the traffic) as close as possible to the beginning of the rule base.
Unfortunately, one cannot reorder the firewall rules arbitrarily when trying to reduce the CPU utilization. Moving a rule from its current position to another may alter the action that the firewall makes on some, or all, of the connections that match the rule that is being moved. Moving a rule R1 closer to the beginning of the rule base may cause it to supersede another rule R2. Such a change could cause some connections that were matched by R2 before the rule-move to now be matched by the earlier R1. If R1 and R2 have different actions (e.g., one is PASS and the other is DROP) then moving R1 to be ahead of R2 changes the filtering policy that the rule-base is enforcing. Therefore, moving R1 to be ahead of R2 is deemed an “unsafe” repositioning.